package com.ctrip.demo.leetcode;

import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;

public class LeetCode30 {

    public static void main(String[] args) {

        String s = "barfoothefoobarman";
        String[] words = new String[]{"foo","bar"};

        System.out.println(new LeetCode30().findSubstring(s, words));

    }

    public List<Integer> findSubstring(String s, String[] words) {
        int n = s.length();
        int m = words.length;
        int w = words[0].length();
        Map<String, Integer> map = new HashMap<>();
        for(String word :words) {
            map.put(word, map.getOrDefault(word, 0) + 1);
        }
        List<Integer> res = new ArrayList<>();
        out:for (int i = 0; i + w * m <=n ; i ++) {
            Map<String, Integer> cur = new HashMap<>();
            String sub = s.substring(i, i + m *w);
            for(int j = 0; j < sub.length(); j += w) {
                String item = sub.substring(j , j + w);
                if (!map.containsKey(item)) {
                    continue out;
                }
                cur.put(item, cur.getOrDefault(item, 0) + 1);
            }
            if (cur.equals(map)) {
                res.add(i);
            }
        }
        return res;
    }
}
